#include <iostream>
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>

using namespace std;

const int SIZE = 9;
const int EMPTY = 0;
const char EMPTY_CHAR = '$';


bool isValid(const vector<vector<int>>& board, int row, int col, int num) {
    // 检查行是否合法
    for (int c = 0; c < SIZE; ++c) {
        if (board[row][c] == num) {
            return false;
        }
    }

    // 检查列是否合法
    for (int r = 0; r < SIZE; ++r) {
        if (board[r][col] == num) {
            return false;
        }
    }

    // 检查九宫格是否合法
    int startRow = 3 * (row / 3);
    int startCol = 3 * (col / 3);
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (board[startRow + r][startCol + c] == num) {
                return false;
            }
        }
    }

    return true;
}

//找到第一个解以后，会立即返回true，之后可以扩展
bool solveSudoku(vector<vector<int>>& board) {
    for (int r = 0; r < SIZE; ++r) {
        for (int c = 0; c < SIZE; ++c) {
            if (board[r][c] == EMPTY) {
                vector<int> nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
                random_device rd;
                mt19937 gen(rd());
                shuffle(nums.begin(), nums.end(), gen);//洗牌

                for (int num : nums) {
                    if (isValid(board, r, c, num)) {
                        board[r][c] = num;
                        if (solveSudoku(board)) {
                            return true;
                        }
                        board[r][c] = EMPTY;//恢复现场
                    }
                }
                return false;
            }
        }
    }
    return true;
}

void generateBlankCells(vector<vector<int>>& board) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, SIZE - 1);//均匀分布

    for (int i = 0; i < SIZE; ++i) {
        int row = dis(gen);
        board[i][row] = EMPTY;
    }
}

void writeSudokuToFile(const vector<vector<int>>& board, const string& filename) {
    ofstream file(filename);
    if (file.is_open()) {
        for (const auto& row : board) {
            for (int num : row) {
                if (num != EMPTY) {
                    file << num << " ";
                }
                else {
                    file << EMPTY_CHAR << " ";
                }
            }
            file << endl;
        }
        file.close();
        cout << "数独局面已成功写入文件：" << filename << endl;
    }
    else {
        cout << "无法打开文件：" << filename << endl;
    }
}

void writeSolutionToFile(const vector<vector<int>>& board, const string& filename) {
    ofstream file(filename);
    if (file.is_open()) {
        for (const auto& row : board) {
            for (int num : row) {
                file << num << " ";
            }
            file << endl;
        }
        file.close();
        cout << "数独解已成功写入文件：" << filename << endl;
    }
    else {
        cout << "无法打开文件：" << filename << endl;
    }
}

bool readSudokuFromFile(vector<vector<int>>& board, const string& filename) {
    ifstream file(filename);
    if (file.is_open()) {
        for (int r = 0; r < SIZE; ++r) {
            for (int c = 0; c < SIZE; ++c) {
                char ch;
                file >> ch;
                if (ch == EMPTY_CHAR) {
                    board[r][c] = EMPTY;
                }
                else {
                    board[r][c] = ch - '0';
                }
            }
        }
        file.close();
        return true;
    }
    else {
        cout << "无法打开文件：" << filename << endl;
        return false;
    }
}

int main() {
    // 创建一个空的9x9数独局面
    vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

    solveSudoku(sudoku);

    // 随机挖去一些空白格
    generateBlankCells(sudoku);

    // 将数独局面写入文件
    writeSudokuToFile(sudoku, "sudoku.txt");

    // 读取数独局面
    vector<vector<int>> solvedSudoku(SIZE, vector<int>(SIZE, 0));
    if (readSudokuFromFile(solvedSudoku, "sudoku.txt")) {
        // 解数独
        if (solveSudoku(solvedSudoku)) {
            // 将解写入文件
            writeSolutionToFile(solvedSudoku, "solution.txt");
        }
        else {
            cout << "数独无解" << endl;
        }
    }

    return 0;
}
